package com.zwx.string.leetcode_7;

/**
 * 最长公共前缀
 * 如果不存在公共前缀，返回空字符串“”
 *
 * @author 文希
 * @create 2019-07-02 22:07
 */
public class FindLongestCommonPrefix {

    /**
     * 因为是公共前缀，我们可以对所有字符串进行排序，这样只需要比较首尾两个字符串的公共前缀即可
     */
    private static String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) {
            return "";
        }
        strs = bubbleSort(strs);
        String stStr = strs[0];
        String finalStr = strs[strs.length - 1];
        int length = (finalStr.length() > strs[0].length()) ? strs[0].length() : finalStr.length();

        for (int i = 0; i < length; ) {
            if (stStr.charAt(i) == finalStr.charAt(i)) {
                i++;
            } else {
                if (i == 0) {
                    return "";
                } else {
                    return stStr.substring(0, i);
                }
            }
        }
        return stStr;
    }

    /**
     * 冒泡排序
     */
    private static String[] bubbleSort(String[] strs) {
        String temp;
        for (int i = 0; i < strs.length; i++) {
            for (int j = i + 1; j < strs.length; j++) {
                if (strs[i].compareTo(strs[j]) > 0) {
                    temp = strs[i];
                    strs[i] = strs[j];
                    strs[j] = temp;
                }
            }
        }
        return strs;
    }

    public static void main(String[] args) {
        String[] strs = {"flower","flow","flight"};
        String s = longestCommonPrefix(strs);
        System.out.println("s = " + s);
    }
}
